package com.wenhai.leetcode.array;

/**
 * https://leetcode-cn.com/problems/sub-sort-lcci/
 *
 * @author wenhai
 * @date   2021/3/31
 */
public class 面试题16_16部分排序 {
    public int[] subSort(int[] array) {
        if (array.length==0) {
            return new int[]{-1, -1};
        }
        int value = array[0];
        int endIndex = -1;
        int startIndex = -1;
        for (int i = 1; i < array.length; i++) {
            if (value > array[i]) {
                endIndex = i;
            } else if (value < array[i]) {
                value = array[i];
            }
        }

        if (endIndex == -1) {
            return new int[]{startIndex, endIndex};
        }

        value = array[array.length - 1];
        for (int i = array.length - 2; i >= 0; i--) {
            if (value < array[i]) {
                startIndex = i;
            } else if (value > array[i]) {
                value = array[i];
            }
        }
        return new int[]{startIndex, endIndex};
    }

    public int[] subSort2(int[] array) {
        if (array.length==0) {
            return new int[]{-1, -1};
        }
        int max = array[0];
        int min = array[array.length-1];
        int endIndex = -1;
        int startIndex = -1;
        for (int i = 0; i < array.length; i++) {
            if (max > array[i]) {
                endIndex = i;
            } else if (max < array[i]) {
                max = array[i];
            }
            if (min < array[array.length - i - 1]) {
                startIndex = i;
            } else if (min > array[array.length - i - 1]) {
                min = array[i];
            }
        }
        return new int[]{startIndex, endIndex};
    }
}
